1. Field of the Invention
The present invention relates to a Galois field arithmetic processor capable of performing various Galois field arithmetic operations.
2. Description of the Related Art
In recent years, error correction code techniques have been closely watched from the viewpoint of the digitization of communications and of improved reliability of storage devices. Error correction code techniques are currently used in modem communications and storing data in storage media such as CDs. Especially in the 21th century when the extension of the digital TV broadcasting is expected, error correction code techniques will become indispensable.
The nucleus of the error correction code technique is the arithmetic operation of the Galois field GF(28). It is expected that the Reed-Solomon code of the Galois field GF(28), for example, will be employed in the standard specification of ADSL and satellite broadcasting and further for digital TV systems using terrestrial transmission.
In common practice, the coder and decoder for performing a Galois arithmetic operation have conventionally been realized with a dedicated circuit. However, the dedicated circuit poses the problem that signals of different specifications cannot be handled successfully. The error correction code has different code lengths and different multiplicities for different applications, and therefore the use of a dedicated circuit for this purpose encounters difficulty in conforming with various specifications.
No available processor has a set of Galois field operation commands. In recent years, however, a Galois field arithmetic processor has been developed for performing a part of the process. This processor is incapable of decoding a Reed-Solomon code in its entirety but can only execute a part of the process. As a result, only one of either the multiplication of the Galois field vector expression or the multiplication of the exponential expression is supported, and the performance of the required process necessitates various pre-processing of the data input to the processor. For versatile programming to be possible with the processor instructions alone, both the performance and an instruction set capable of executing a program in its entirety are required. Cooperation between the processor and a dedicated circuit for performing a part of the process is difficult to control and encounters the problem of a reduced performance. In realizing the processing system for the Galois field operation with a processor, compatibility is required between an increased processing speed, a circuit scale must be reduced to less than the dedicated circuit and affinity to the existing pipelines must be provided.
For the power operation, on the other hand, the arithmetic operation between exponents with 255 as a modulus such as (xcex1i)j=xcex1i*j is a common practice. The syndrome operation, therefore, requires conversion of the operation result for use in the next operation. This process cannot be performed by the processor alone. When the power operation is performed by multiplication between exponents, an increased arithmetic unit size poses a problem. In other words, it is necessary to include a special circuit in the form of an arithmetic multiplier with 255 as a modulus in the Galois field FG (28) arithmetic unit, resulting in a great disadvantage from the viewpoint of hardware utilization efficiency.
The object of the present invention is to realize a practical processor with a simple configuration which solves the problem points described above.
FIG. 1 is a diagram showing a first basic configuration of a Galois field arithmetic processor according to the invention. As shown in FIG. 1, the Galois field arithmetic processor according to the invention has the feature in that a data conversion circuit is arranged to perform the conversion of only one operand, and operands of different expressions can be processed as they are.
Specifically, a Galois field arithmetic processor according to this invention comprises an instruction decoder 1, and an arithmetic unit including a Galois field vector adder 31, a Galois field vector multiplier 32, and a Galois field exponential adder-subtractor 33 for executing the Galois field operation on the first and second operands.
In the case where the arithmetic unit 30 includes at least the Galois field vector adder 31 and the Galois field vector multiplier 32, for example, an exponent-vector conversion circuit 22 for converting the second operand from the exponential expression to the vectorial expression is provided with an instruction for performing the Galois field arithmetic operation on the first operand expressed vectorially and the second operand expressed exponentially. With this configuration, if it is assumed that the data expressed vectorially is input as the first operand and the data expressed exponentially is the second operand, the second operand is converted into a vectorial expression by the conversion circuit, after which the Galois field vector adder or the Galois field vector multiplier performs the arithmetic operation. This function is effective for arithmetically processing r*Gxcex1i, for example, from the vectorial expression r and the exponential expression i, and a single instruction can be realized with which to execute the aforementioned operation of the processor.
If it is assumed that a selector 55 is provided for selecting the second operand or the output of the exponent-vector conversion circuit 22 and supplying the choice as a second operand to the arithmetic unit 30, then, both the data vectorially expressed and the data exponentially expressed can be input as the second operand, and the processor can be provided with an instruction for performing the Galois field operation on the two vectorially expressed data. Further, providing a second input data selector 51 for selecting the second operand or the processing result and outputting the choice as the second operand, the arithmetic operation can be repeated on the operation result requiring the conversion.
Also, in the case where the arithmetic unit 30 includes at least a Galois field exponential adder-subtractor 33, a vector-exponent conversion circuit 21 is provided for converting the second operand from a vectorial expression to an exponential expression, with an instruction for performing the Galois field operation on the exponentially expressed first operand and the vectorially expressed second operand. In this configuration, assume that the data exponentially expressed and the data vectorially expressed are input as the first operand and the second operand, respectively. The second operand is converted into an exponential expression by the conversion circuit, after which the Galois field exponential adder-subtractor performs the arithmetic operation. In the case of GF(28), the addition-subtraction is conducted, for example, with 255 as a modulus in the following manner.
(100+30)mod255=(130)mod255=130
(200+57)mod255=(257)mod255=2
(57xe2x88x92200)mod255=(xe2x88x92143)mod255=112
This function is effective for processing i+Aj or ixe2x88x92Aj (addition-subtraction between exponents i and j), for example, from the vectorial expression a(xcex1i) and the exponential expression j, and the operation can be performed by giving a single instruction to the processor. Further, if j=0, the conversion is simply the one from a vectorial expression to an exponential expression.
In similar fashion, assume that a selector 55 is added for selecting either the second operand or the output of the vector-exponent conversion circuit 21, and the result is supplied as the second operand to the arithmetic unit 30. Then, either the exponentially expressed data or the vectorially expressed data can be input as the second operand, and an instruction to the processor can be provided for the Galois field operation on two exponentially expressed data.
In the configuration described above, the conversion table is provided only for one operand, and therefore the expression of the first and second operands is restricted. By selecting the operand to be input, in accordance with a particular expression, however, various operation requirements can be met sufficiently, and no practical problem is posed. The configuration according to the invention requires substantially no conversion for the two operands, and such a requirement, if any, can be met by combining two instructions. In the case where a higher versatility is needed, the two configurations described above are combined in such a manner that the arithmetic unit 30 includes a Galois field vector adder 31, a Galois field vector multiplier 32, a Galois field exponential adder-subtractor 33, a vector-exponent conversion circuit 21 and an exponent-vector conversion circuit 22. Then, a greater multiplicity of operation instructions can be executed. Reference numeral 11 designates a first operand register for holding the first operand temporarily, numeral 12 designates a second operand register for holding the second operand temporarily, numeral 61 a first arithmetic data selector for selecting the output of the first operand register 11 and the previous operation result and outputting it as the first operand to the arithmetic unit 30, numeral 62 a second arithmetic data selector for selecting either the output of the selector 55 or the previous operation result and outputting it as the second operand to the arithmetic unit 30, whereby the operation result can be processed repeatedly without conversion. Also, reference numeral 65 designates a selector for selecting the output of the arithmetic means used.
FIG. 2 is a diagram showing a second basic configuration of a Galois field arithmetic processor according to the invention. In this processor, the arithmetic unit includes a Galois field exponential adder-subtractor 33, a vector-exponent conversion circuit 21 as a conversion table, a first input selector 52 for selecting the first or the second operand input thereto and a second input selector 53 for selecting the first or second operand. This configuration permits the operation of not only i+Aj or ixe2x88x92Aj (addition-subtraction between exponents i and j) but also j+Ai or jxe2x88x92Ai as well when the vectorial expression a(xcex1i) and the exponential expression j are given. By setting j=0 in the operation jxe2x88x92Ai, the exponential expression of an inverse element to the vectorial expression a(xcex1i) can be executed with a single instruction. The Galois field division is possible with two instructions, for example, by adding the configuration of FIG. 2 to the configuration of FIG. 1, and inputting, as the second operand in the configuration of FIG. 1, the exponential expression of the inverse element to the vectorial expression a determined as described above. In the prior art, the inverse element of the vectorial expression is determined by providing an inverse element table. However, this table is used only for this purpose, and is increasingly a problem as the circuit size increases. This invention avoids such a problem.
FIG. 3 is a diagram showing a third basic configuration of the Galois field arithmetic processor according to the invention. As shown in FIG. 3, this process has the feature in that a third operand is input, and the arithmetic unit 30 is so configured that the first and second operation data are applied to the Galois field vector multiplier 32 and the output of the Galois field vector multiplier 32 and the third operand are output to the Galois field vector adder 34. The configuration of FIG. 3 further includes an accumulator 35 for temporarily holding the output of the Galois field vector adder 34, a first operand selector 62 for selecting the first operand and the output of the accumulator 35 and outputting the choice as the first operand to the Galois field vector multiplier 32, and a third operand selector 63 for selecting either the third operand or the output of the accumulator 35 and outputting the choice as the third operand to the Galois field vector adder 34. Also, the third operand register 13 temporarily holds the third operand.
The configuration of FIG. 3 makes possible the arithmetic operation such as (first operand)*G(second operand)+G (third operand)xe2x86x92first operand, or the sum of normal products such as (first operand)*G(second operand). The syndrome operation performed for error correction in the Reed-Solomon code, for example, requires the following arithmetic operation.                               S          3                =                                            r                              n                -                1                                      *            G            ⁢                          xe2x80x83                        ⁢                          α                                                (                                      n                    -                    1                                    )                                ⁢                i                                              +                                    Gr                              n                -                2                                      *            G            ⁢                          xe2x80x83                        ⁢                          α                                                (                                      n                    -                    2                                    )                                ⁢                i                                              +                      G            ⁢                          xe2x80x83                        ⁢            …                    +                                    Gr              1                        ⁢                          α              i                                +          Gr0                                        =                  (                      xe2x80x83                    ⁢                                    …              ⁢                              xe2x80x83                            ⁢                              (                                                                            (                                                                                                    r                                                          n                              -                              1                                                                                *                          G                          ⁢                                                      xe2x80x83                                                    ⁢                                                      α                            i                                                                          +                                                  Gr                                                      n                            -                            2                                                                                              )                                        *                    G                    ⁢                                          xe2x80x83                                        ⁢                                          α                      i                                                        +                  …                  +                                      Gr                    i                                                  )                            *              G              ⁢                              xe2x80x83                            ⁢                              α                i                                      +                          Gr              0                                          
In this arithmetic operation, the part of the operation xe2x80x9c(first operand)*G(second operand)+G (third operand)xe2x86x92first operandxe2x80x9d is effective. In this operation, xcex1i is given as a vectorial expression or as an exponential expression of the Galois field GF(28), to either of which the present invention is applicable. This operation eliminates the need of the third operand selector 63, although the provision of the third operand selector 63 makes normal operation of the sum of products possible. In such a case, the first operand selector 62 is not necessary. The chain search for error correction in the Reed-Solomon code is an operation of substituting into polynomials and can be performed by the operation of the sum of products.
The accumulator 35 included in the configuration of FIG. 3 may be replaced with a selector for selecting the first operand and the operation result or a selector for selecting the third operand and the operation result, and the operation result may be returned as the first or third operand.
In the Galois field arithmetic processor having the conversion table as mentioned above, a high operation speed can be achieved by dividing the conversion process and the arithmetic process with the arithmetic unit into two stages and performing them concurrently by pipelining.
The pipelining process requires a temporary holding register including a flip-flop or the like for holding the data temporarily in the connection of each stage. The instruction decoder 1 outputs the control data for controlling such temporary holding registers. Further, in the case where a feedback mechanism having a selector for returning the operation result as the second operand is provided in order to perform the repetitive operations using the previous operation result, the control data for this feedback mechanism is also output from the instruction decoder 1. Also, for sequentially transmitting the control data to the stages corresponding to each temporary holding register and the selector of the feedback mechanism, a control decision circuit is configured with a transmission register. The control decision circuit decides whether control data are for controlling a corresponding register or selector and in accordance with the decision, generates a control signal for controlling the register or selector, as the case may be. In the case where the operation result is used as the next second operand, the conversion may or may not be required. In such a case, a stage flag indicating the presence or absence of the processing in the first stage is incorporated in the control data of the selector of the feedback mechanism. Thus, the control decision circuit corresponding to the feedback mechanism generates a control signal for bypassing the process of the first stage in accordance with the stage flag status.
Also in the operation of GF(2m), the exponent constituting an operand never exceeds m bits, nor does the result of addition/subtraction exceed m bits as it is performed with 2mxe2x88x921 as a modulus. The vector operation of course involves m bits, and therefore the data width is kept fixed in the operation. Thus, m-bit operations in the number of n can be concurrently performed with a fixed data width of mxc3x97n. Assume, for example, that the operation of the Reed-Solomon code of GF(28) is incorporated in a processor having a data (register) width of 32 bits. The operation can be carried out in four parallel stages without changing the register port, the operand bus, the result bus or the bypass mechanism but simply by arranging the conversion tables and the arithmetic means in four parallel stages.
In the n parallel operations described above, it is desirable to provide a flag storage register for storing n-bit flags in continuous areas indicating that the result of operation in n arithmetic means is zero. In this way, as compared with the case where the flags are distributed, a program can be realized which facilitates the substitution operation in the chain search.
Also, an accumulation flag is desirably provided for accumulating the zero flags by calculating the logic sum of the output of the Galois field vector adder and the previous output thereof. In the n parallel operations as described above, n accumulation flags are provided and an immediate value copy register is desirably provided for storing arbitrary m-bit data at n points, indicated as the immediate value of the second operand. As a result, the division of polynomials required for the Euclidean algorithm is facilitated in the coding and decoding of the Reed-Solomon code.
Also, in the case where the conversion circuit described above is realized by a table in a memory, a memory built in the processor may be used. When n processes are conducted in parallel, however, n different addresses are required to be input. In view of this, n memories with a data width m are used to constitute n banks and hence n accessible memories. At the same time, a memory having a data width mxc3x97n accessible by a common address is constituted.
The exponential expression of 2mxe2x88x921 desirably corresponds to the vectorial expression of zero in the Galois field arithmetic processor, while 2mxe2x88x921 is desirably output in response to an input of 2mxe2x88x921 in the Galois field adder-subtractor. The zero vector of GF(2m) cannot be expressed by the exponential indication of xcex1i.
Assuming that 2mxe2x88x921 is t in GF(2m), xcex1t=xcex10. This is inconvenient for the operation. For example, if it is considered that the chain search of GF(2m) in the Reed-Solomon decode algorithm in which four substitution operations of polynomials are executed in parallel, and when the result becomes zero as in the case described above, the flag is stored in the flag storage register. Substituting units of 4k to 4k+3 into i, i=252, 253, 254, 255 are processed with a single instruction. If i =0 is the resolution of the search, i=255 is also stored in memory as a resolution. Excluding this requires a program for processing i=255 specially. In the case where i=255 is converted into a vector of zero, on the other hand, the substitution operation in the chain search always results in xcex10=(00000001) and zero is basically excluded. Thus the search is possible without forming a program for excluding i=255.
When converting the vectorial expression of zero into an exponential expression, on the other hand, an arrangement may be made not to output data. It is more useful, however, to output an established value. In the case where 255 is input to an operand register in the addition of exponents, for example, the output may be set to 255 regardless of the result of addition. In the multiplication of the Galois field GF(28), this corresponds to the fact that the result of multiplication of the 0 vector is always the zero vector. Also in the exponential subtraction, the result of inputting 255 to any one of the operand registers may be set to 255. In the case where 255 is input as a minuend, the result of dividing the zero vector by whatever value becomes 0 vector. In the case where 255 is input as a subtrahend, on the other hand, the division by zero is not definable.
A Galois field arithmetic processor according to another aspect of the invention comprises an arithmetic unit including an instruction decoder, a first Galois field vector multiplier having two input terminals each supplied with a first operand and a second Galois field vector multiplier having two input terminals supplied with the first operand and the the result of arithmetic operation, respectively, a one-bit shifter for counting the number of times indicated by the second operand, an accumulator for temporarily holding the output of the second Galois field vector multiplier and supplying it to the other input terminal of the second Galois field vector multiplier, a first input selector for selecting the first operand or the output of the first Galois field vector multiplier, and a second input selector for selecting the second operand or the output of the one-bit shifter and outputting it as the second operand. This Galois field arithmetic processor is suitable for determining ap from the vectorially expressed a and the number of power p.
Also in this configuration, n operations having a data width m can be performed in parallel. Also, by inputting a as the first operand and the exponent 2 as the second operand, the conversion from an exponential expression to a vectorial expression can be performed. In the case where this conversion is performed as a table conversion using a memory, the capacity of 2mxc3x97m bits is required, thereby increasing the hardware amount exponentially in accordance with m. Therefore, this configuration is effective especially for a large m.